import java.util.ArrayList;


public class InsertionSort {


	
	public static Comparable[] sort(Comparable[] list){
		
		insertionSort(list);
		/*long stappenteller = 0;
		long starttijd = System.nanoTime();
		for(int index=1; index<list.length; index++){
			Comparable hulp = list[index];
			int vorige = index-1;
			while(vorige>=0 && hulp.compareTo(list[vorige])==-1){
				//list[vorige+1] = list[index];
				QuickSort.verruil(list, vorige+1, index);
				vorige--;
				stappenteller++;
			}
			stappenteller++;
		list[vorige+1] = hulp;
		}
		long looptijd = System.nanoTime()-starttijd;
		
		*/return list;
	}

	
	/**
	* Simple insertion sort.
	* @param a an array of Comparable items.
	*/
	public static <AnyType extends Comparable<? super AnyType>>
	void insertionSort( AnyType [ ] a )
	{
		long stappenteller = 0;
		for( int p = 1; p < a.length; p++ )
		{
			AnyType tmp = a[ p ];
			int j = p;

			for( ; j > 0 && tmp.compareTo( a[ j - 1 ] ) < 0; j-- ){
				a[ j ] = a[ j - 1 ];
				stappenteller++;
			}
			stappenteller++;	
			a[ j ] = tmp;
		}
		System.out.println("InsertionSort resolved in: " + stappenteller);
	}


}
